package test;

import java.util.*;

/**
 * @Author: gc
 * @Date: 2024/6/27 11:02
 * @explain:
 **/
public class test {
    public static final int N = 65535;//表示顶点之间不直接连通

    public static void main(String[] args) {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //顶点到自身距离为0
        int[][] matrix = {
                {0, 12, N, N, N, 16, 14},
                {12, 0, 10, N, N, 7, N},
                {N, 10, 0, 3, 5, 6, N},
                {N, N, 3, 0, 4, N, N},
                {N, N, 5, 4, 0, 2, 8},
                {16, 7, 6, N, 2, 0, 9},
                {14, N, N, N, 8, 9, 0}
        };
        Graph graph = new Graph(matrix, vertex);
        graph.floyd();
        graph.result();
    }
}

//带权无向图
class Graph {
    public char[] vertex;//存放顶点
    public int[][] matrix;//保存各个顶点到其它顶点的距离，初始为直接连接的距离，算法计算后为最短距离
    public int[][] relay;//保存中间结点

    //构造器
    public Graph(int[][] matrix, char[] vertex) {
        this.vertex = vertex;
        this.matrix = matrix;
        this.relay = new int[vertex.length][vertex.length];
        //三个点为同一顶点时：中间顶点为自身；三个点是不同顶点时：中间顶点是终点的前驱节点；两个顶点直接连通时：中间节点为出发点
        for (int i = 0; i < vertex.length; i++) {
            Arrays.fill(relay[i], i);//初始中间顶点为自身
        }
    }

    //显示算法结果
    public void result() {
        for (int k = 0; k < vertex.length; k++) {
            for (int i = 0; i < vertex.length; i++) {
                System.out.println(vertex[k] + " 到 " + vertex[i] +
                        " 最短路径 " + matrix[k][i] +
                        " 中间结点 " + vertex[relay[k][i]]+
                        " xiabiao "+relay[k][i]);
            }
            System.out.println();
        }
    }

    //弗洛伊德算法
    public void floyd() {
        //保存i到j的距离
        int temp;
        Map<Integer,Integer> code = new HashMap<>();
        List<Map> list = new ArrayList<>();
        for (int i = 0; i < matrix.length; i++) {//出发点i
            for (int j = 0; j < matrix.length; j++) {//中间顶点j
                for (int k = 0; k < matrix.length; k++) {//终点k
                    temp = matrix[i][j] + matrix[j][k];//求从i出发，经过k，到达j的距离
                    if (temp < matrix[i][k]) {
                        matrix[i][k] = temp;//更新距离
                        relay[i][k] = relay[j][k];//更新中间顶点
                    }
                }
                list.add(code);
            }
        }
        System.out.println(list);
    }
}
